/*
 输入由多个测试用例。每个测试用例的第一行包含三个整数N，M，和T（n，m <7 <1; <T <50 0），这表示迷宫的大小，
 T表示时间，接下来的N行给出迷宫的布局，字符是下列之一：

'X'：墙，小狗不能进入;
“S”：小狗的起点;
'D'：门，终点
'.'：一个空地。

The input is terminated with three 0's. This test case is not to be processed.
Output
For each test case, print in one line "YES" if the doggie can survive, or "NO" otherwise.
Sample Input
4 4 5
S.X.
..X.
..XD
....
3 4 5
S.X.
..X.
...D
0 0 0
Sample Output
NO
YES
-------------------------------------------
分析：本题涉及到深度搜索（当然也可以广度搜索）+剪枝，典型的迷宫问题。问题的大概意思是，
狗在S点，门在D点，门只有在T时刻才开，迷宫为N*M矩阵，迷宫内有X代表的墙。问是否狗能准时逃出来。
我们要制造一个计划，让狗能在T时刻刚好到达门口，一般思路可以来回走动，快到T时候再到门口。
但是题目要求狗每次走的地方都将会陷下去，不能回走，只能绕路走，
能绕路走可定要多出偶数的步数，就算是墙挡着也一样如此，所以奇数的话要剪枝掉，省掉搜索时间。
而另一个剪枝，路径剪枝，是在开始的时候，将如迷宫的每个地方都走过了，而还没到门开的时间，
这时也逃生不了，因为没地方回走了，都塌陷了。 深度搜索下去，直到所用的步数刚好等于给定的T时间，退出递归搜索。
 */
package com.yuan.algorithms.practice201503;

import java.util.Scanner;

public class 小狗走迷宫 {

	static char[][] map;
	static int timeSum;//用时
	static boolean mark[][];//标记地图是否已经走过
	static boolean P;//标记是否可以到达终点
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while (sc.hasNext()) {
			int n = sc.nextInt();
			int m =sc.nextInt();
			int time = sc.nextInt();
			if (n==0 && m==0 && time==0) {
				continue;
			}
			timeSum = 0;
			map = new char[n][m];
			mark = new boolean[n][m];
			P = false;
			for (int i = 0; i < n; i++) {
				String a = sc.next();
				for (int j = 0; j < m; j++) {
					map[i][j] = a.charAt(j); 
				}
			}
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < m; j++) {
					if (map[i][j]=='S') {
						f(i,j,0);
						break;
					}
				}
			}
			System.out.println(timeSum);
			if (P) {//判断是否到达终点
				if (timeSum<=time) {
					System.out.println("YES");
				}else {
					System.out.println("NO");
				}
			}else {
				System.out.println("NO");
			}
		}

	}
	
	/**
	 * 
	 * @param i 地图横坐标
	 * @param j 地图纵坐标
	 * @param t 记录的步数
	 */
	private static void f(int i, int j, int t) {
		if ( i>=map.length || j>=map[0].length || i<0 || j<0 || map[i][j]=='X' ) {
			return;
		}else if (map[i][j]=='D') {
			P = true;//标记达到终点
			timeSum = t;
			return;
		}
		
		if (!mark[i][j]) {
			mark[i][j] = true; 
			f(i+1, j, t+1);//下
			f(i, j+1, t+1);//右
			f(i-1, j, t+1);//上
			f(i, j-1, t+1);//左
			//mark[i][j] = true; 
		}
	}

}
